#pragma once
#include<vector>
enum State
{
	EMPTY,
	EXIST,
	DELETE
};

template<class K ,class V>
struct HashData
{
	pair<K, V> _kv;
	State _st;
};


template<class K>
class HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

struct HashFuncString
{
	
	size_t operator()(const string& s)
	{
		size_t sum = 0;
		for (auto e: s)
		{
			sum += e;
			sum *= 131;
		}
		return sum;
	}
};

template<class K, class V>
class HashTable
{
public:
	HashTable(size_t size = 10)
	{
		_tables.resize(size);
	}

	HashData<K, V>* Find(const K& key)
	{
		size_t hashi = key % _tables.size();
		while (_tables[hashi]._st != EMPTY)
		{
			if (_tables[hashi]._kv.first == key && _tables[hashi]._st != DELETE)
			{
				return &_tables[hashi];
			}
			hashi++;
			hashi %= _tables.size();
		}
		return nullptr;
	}

	bool Insert(const pair<K, V>& kv)
	{

		if (_n * 10 / _tables.size() >= 7)
		{
			HashTable<K,V> newHT(_tables.size() * 2);
			for (auto& e : _tables)
			{
				if(e._st == EXIST)
				newHT.Insert(e._kv);
			}
			_tables.swap(newHT._tables);
		}

		size_t hashi = kv.first % _tables.size();
		while (_tables[hashi]._st == EXIST)
		{
			hashi++;
			hashi %= _tables.size();
		}
		_tables[hashi]._kv = kv;
		_tables[hashi]._st = EXIST;
		_n++;
		return true;
	}

	bool Erase(const K& key)
	{
		HashData<K,V>* ret = Find(key);
		if (ret != nullptr)
		{
			_n--;
			ret->_st = DELETE;
			return true;
		}
		else
		{
			return false;
		}
	}

private:
	vector<HashData<K, V>> _tables;
	int _n;
};

void TestHT1()
{
	int a[] = { 1,4,24,34,7,44,17,37 };
	HashTable<int, int> ht;
	for (auto e : a)
	{
		ht.Insert(make_pair(e, e));
	}

	for (auto e : a)
	{
		auto ret = ht.Find(e);
		if (ret)
		{
			cout << ret->_kv.first << ":E" << endl;
		}
		else
		{
			cout << e << ":D" << endl;
		}
	}
	cout << endl;

	ht.Erase(34);
	ht.Erase(4);

	for (auto e : a)
	{
		auto ret = ht.Find(e);
		if (ret)
		{
			cout << ret->_kv.first << ":E" << endl;
		}
		else
		{
			cout << e << ":D" << endl;
		}
	}
	cout << endl;
}

